用python求素数的方法，以及一种算法优化

#用python求素数的方法，以及一种算法优化| 来源: 网络整理| 查看: 265

python求素数前言方法一1、代码2、输出结果方法二1、代码2、输出结果

前言

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数(该解释来自百度百科)。如果要找100以内的素数，我们可以寻找100以内的非素数，即证明一个数除了1和它本身以外还可以被其他自然数整除，不能被证明的数就是素数。

方法一 1、代码

代码如下：

list1 = [1, 2] for i in range(2, 101): for j in range(2, i): if i % j == 0: break elif j == i-1: list1.append(i) print(list1) 2、输出结果 [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] Process finished with exit code 0

我们只需要让2到n-1中间所有的数除n，只要结果为0循环提前结束，如果n-1也验证过依然没有提前结束循环，此时这个数为素数，计入列表中。

方法二

当我们遇见较大的数值，比如100000时，使用方法一的效率显然会很慢，这时候就需要对素数的特性有一个更深的了解，以此来优化算法

1、代码 list1 = [1, 2] for i in range(2, 101): for j in list1[1:]: if i % j == 0: break elif i

【本文地址】

公司简介

联系我们